package lcr;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test0007 {
    public static void main(String[] args) {
        int[] nums = {-1,0,1,2,-1,-4};
        Solution0007_1 solution = new Solution0007_1();
        int[][] ans = solution.threeSum(nums);
        for (int i = 0; i < ans.length; i++) {
            for (int j = 0; j < ans[i].length; j++) {
                System.out.print(ans[i][j]+" ");
            }
        }
    }
}
class Solution0007_1 {
    public int[][] threeSum(int[] nums) {
        ArrayList<List<Integer>> lists = new ArrayList<>();
        Arrays.sort(nums);
        int start = 0,length = nums.length;
        while (start< length&&nums[start]<=0){
            caculate(nums,start,lists);
            start=next(nums,start);
        }

        int[][] ans = new int[lists.size()][3];
        for (int i = 0; i < lists.size(); i++) {
            List<Integer> list = lists.get(i);
            for (int j = 0; j < 3; j++) {
                ans[i][j]= list.get(j);
            }
        }
        return ans;
    }

    public void caculate(int[] nums, int start, ArrayList<List<Integer>> lists){
        int l=start+1, r=nums.length-1;
        int numS = nums[start];
        while (l<r){
            int sum = numS +nums[l]+nums[r];
            if (sum<0){
                l=next(nums,l);
            }else if (sum>0){
                r=last(nums,r);
            }else {
                lists.add(List.of(numS,nums[l],nums[r]));
                l=next(nums,l);
                r=last(nums,r);
            }
        }
    }

    public int last(int[] nums, int index){
        int now = nums[index];
        while (index >= 0 && nums[index] == now){
            index--;
        }
        return index;
    }

    public int next(int[] nums, int index){
        int now = nums[index];
        while (index < nums.length && nums[index] == now){
            index++;
        }
        return index;
    }
}
